Paper 2014/1029

On the Cryptographic Hardness of Finding a Nash Equilibrium

Nir Bitansky, Omer Paneth, and Alon Rosen

Abstract

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is known to be complete. Previous proposals for basing PPAD-hardness on program obfuscation considered a strong “virtual black-box” notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps. Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. FOCS 2015
Keywords
obfuscationnash equilibriumPPADcryptographic hardness
Contact author(s)
nirbitan @ csail mit edu
History
2015-08-14: revised
2015-01-02: received
See all versions
Short URL
https://ia.cr/2014/1029
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/1029,
      author = {Nir Bitansky and Omer Paneth and Alon Rosen},
      title = {On the Cryptographic Hardness of Finding a Nash Equilibrium},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/1029},
      year = {2014},
      url = {https://eprint.iacr.org/2014/1029}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.